# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=27
    
    PROBLEM
    
    Euler published the remarkable quadratic formula:

    n² + n + 41

    It turns out that the formula will produce 40 primes for the consecutive
    values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41
    is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly
    divisible by 41.

    Using computers, the incredible formula  n² − 79n + 1601 was discovered,
    which produces 80 primes for the consecutive values n = 0 to 79. The
    product of the coefficients, −79 and 1601, is −126479.

    Considering quadratics of the form:

        n² + an + b, where |a| < 1000 and |b| < 1000

        where |n| is the modulus/absolute value of n
        e.g. |11| = 11 and |−4| = 4

    Find the product of the coefficients, a and b, for the quadratic
    expression that produces the maximum number of primes for consecutive
    values of n, starting with n = 0.

    
    NOTES
    The problem is stated somewhat ambiguously, but it appears most people
    intepreted last line to indicate the sequence of consecutive primes must
    start with 0, which admits more shortcuts. Also possible that longest
    sequence will start with 0.
    
    Possible Shortcuts:
        Rule out certain values of a
        Rule out certain values of b
        Rule out certain valus of (a, b)
    
    Observations:
        n^2 + an + b -> n(n + a) + b
        
    Hypotheses:
    1.  Longest possible streak is no greater than smallest prime factor of
        abs b. Hence b should be prime.
    2. If last line interpreted correctly as noted above, a + 1 + b must be
        prime.
    
    Some failed shortcut hypotheses:
    1.  Quadratic will be prime if b is not even divisible by n or n + a
    2.  Quadratic will be prime if b does not share a prime factor with n or
        n+a
        
    
    REFERENCES
    http://primes.utm.edu/notes/faq/negative_primes.html
    
    
    PERFORMANCE
    time <final solution>: 7.487584 s
    time <first solution>: 467.627319 s
    
"""
#
# Import
#
import time
import random


#
# Globals / Constants
#
EULER_LIMIT = 40

def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    f = "value %s != expected %s"
    f = message != '' and f + " (%s)" or f + "%s"
    assert value == expected, f % (value, expected, message)


#
# Test Case / Solution
#
@timeit    
def test_case():    
    # is prime
    cases = [
        # n, a, b, expected
        (0, 1, 41, True),
        (39, 1, 41, True),
        (40, 1, 41, False),
        (41, 1, 41, False),
        (0, -79, 1601, True),
        (79, -79, 1601, True),
        (80, -79, 1601, False)
    ]
    
    for n, a, b, expected in cases:
        is_prime_ = is_prime(quadratic_formula(n, a, b))
        assert_match(is_prime_, expected, (n, a, b))
    
    cases = [
        # a, b, expected consecutive primes
        (1, 41, 40),
        (-79, 1601, 80)
    ]
    
    for a, b, expected in cases:
        consecutive_primes = find_max_consecutive_primes(a, b)
        assert_match(consecutive_primes, expected)
    
    print "test case passed!"

@timeit
def solution():
    return find_product_longest_sequence()

#
# Solution Code
#
def find_product_longest_sequence():
    max_ab = None
    max_sequence = EULER_LIMIT
    
    for a in xrange(-999, 1000):
        for b in xrange(-999, 1000):
            if not is_prime(b) or b < max_sequence:
                continue
            consecutive_primes = find_consecutive_primes_from_0(a, b)
            if consecutive_primes > max_sequence:
                max_sequence = consecutive_primes
                max_ab = (a, b)
                print (a, b), max_sequence
                
    return max_ab[0] * max_ab[1]
    
def first_solution():
    """time <function solution at 0x7f5784a0c7d0>: 467.627319 s"""
    max_ab = None
    max_max = EULER_LIMIT
        
    for a in xrange(-999, 1000):
        #if a % 100 == 0: print a
        for b in xrange(-999, 1000):
            if not is_prime(b) or b < max_max:
                continue
            #print (a,b),
            max_consecutive_primes = find_max_consecutive_primes(a, b)
            if max_consecutive_primes > max_max:
                max_max = max_consecutive_primes
                max_ab = (a, b)
                print (a, b), max_max
                
    return max_ab[0] * max_ab[1]

def find_consecutive_primes_from_0(a, b):
    consecutive_primes = 0
    
    for n in xrange(b):
        if is_prime(quadratic_formula(n, a, b)):
            consecutive_primes += 1
        else:
            return consecutive_primes
            
    return consecutive_primes

def find_max_consecutive_primes(a, b):
    max_consecutive_primes = 0
    consecutive_primes = 0
    
    for n in xrange(b):
        #print n, quadratic_formula(n, a, b)
        if is_prime(quadratic_formula(n, a, b)):
            consecutive_primes += 1
        else:
            max_consecutive_primes = max([consecutive_primes,
                max_consecutive_primes])
            consecutive_primes = 0
            
    return max_consecutive_primes
   
def quadratic_formula(n, a, b):
    return n*(n+a) + b

def is_prime(number):
    if number <= 1:
        return False
    
    max_factor = int(round(number**0.5)) + 1
    
    for n in xrange(2, max_factor):
        if number % n == 0:
            return False
        
    return True

def get_prime_factors(number):
    for n in xrange(2, number):
        if number % n == 0:
            return get_prime_factors(n) + get_prime_factors(number / n)
    return [number]
    
def get_common_factors(n1, n2):
    return set(get_prime_factors(n1)).intersection(set(get_prime_factors(n2)))
    
def get_smallest_prime_factor(number):
    for n in xrange(2, number):
        if number % n == 0:
            return n
    return number


#
# Additional Tests
#
def test_h1():
    """longest possible streak is no greater than smallest prime factor of
    abs b"""
    rand_n = lambda: random.randint(0, 1000)
    rand_ab = lambda: random.randint(-999, 1000)
    
    for n in range(1000):
        n, a, b = rand_n(), rand_ab(), rand_ab()
        
        abs_b = abs(b)
        spf = get_smallest_prime_factor(abs_b)
        max_consecutive_primes = find_max_consecutive_primes(a, b)
        
        #print (a, b), spf, max_consecutive_primes
        assert max_consecutive_primes <= spf, "hypothesis 1 rejected"
        
    print "hypothesis 1 confirmed!"
        
        
def test_h2():
    """ """
    rand_n = lambda: random.randint(0, 1000)
    rand_ab = lambda: random.randint(-999, 1000)
    
    def is_prime_quadratic(n, a, b):
        if n*(n+a) + b < 2:
            return False
        
        b_primes = set(get_prime_factors(abs(b)))
        n_primes = set(get_prime_factors(abs(n)))
        #print (b_primes, n_primes, b_primes.intersection(n_primes))
        if b_primes.intersection(n_primes):
            return False
        
        na_primes = set(get_prime_factors(abs(n+a)))
        #print (b_primes, na_primes, b_primes.intersection(na_primes))
        if b_primes.intersection(na_primes):
            return False
        
        return True
    
    for n in range(1000):
        n, a, b = rand_n(), rand_ab(), rand_ab()
        
        is_prime_q = is_prime_quadratic(n, a, b)
        is_prime_a = is_prime(quadratic_formula(n, a, b))
        
        print (n, a, b), (is_prime_q, is_prime_a,), (
            get_prime_factors(abs(b))), (
            quadratic_formula(n, a, b),
            get_prime_factors(quadratic_formula(n, a, b)))
        assert_match(is_prime_q, is_prime_a, "hypothesis 2 rejected")
        
    print "hypothesis 2 confirmed!"


#
# Main
#
if __name__ == '__main__':
    test_h1()
    #test_h2()
    test_case()
    print solution()
    